/**
 * 
 */
package cn.edu.ustc.multicore.exercise.ch2;

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
import java.util.concurrent.TimeUnit;

import cn.edu.ustc.multicore.exercise.ch1.PrimeSearching;

/**
 * @author allewang
 * 
 */
public class LongestSerialSearch extends RecursiveAction {

	private int[] numbers;
	private int low;
	private int high;
	private LongestSerial result;

	public LongestSerialSearch(int[] numbers, int low, int high,
			LongestSerial result) {
		this.numbers = numbers;
		this.low = low;
		this.high = high;
		this.result = result;
	}

	/**
	 * @Override
	 */
	protected void compute() {
		// end of division
		if (low == high)
			return;

		// try find the position where the previous and after are different from
		// the middle position of number array
		int mid = (low + high) / 2;
		int dividePosStart = mid;
		int dividePosEnd = mid;

		// search divide position from middle to array head where the number is
		// different with previous
		while (dividePosStart > low
				&& numbers[dividePosStart] == numbers[dividePosStart - 1]) {
			dividePosStart--;
		}
		// search divide position from middle to array tail where the number is
		// different with later
		while (dividePosEnd < high
				&& numbers[dividePosEnd] == numbers[dividePosEnd + 1]) {
			dividePosEnd++;
		}

		int serailLen = dividePosEnd - dividePosStart + 1;
		if (serailLen > result.len) {
			result.len = serailLen;
			result.pos = dividePosStart;
		}

		if (dividePosEnd < high)
			dividePosEnd++;

		LongestSerialSearch left = new LongestSerialSearch(numbers, low,
				dividePosStart, result);
		LongestSerialSearch right = new LongestSerialSearch(numbers,
				dividePosEnd, high, result);
		left.fork();
		right.compute();

	}

	/**
	 * Generate number array randomly
	 * 
	 * @param length
	 * @return
	 */
	private static int[] RandomCreateArray(int length, int bound) {
		System.out.println("Generating numbers[] randomlly, and its unit number between [0 ~ "+bound+"]");
		System.out.println("numbers[" + length + "]=[");
		int[] numbers = new int[length];
		int max = bound;
		for (int i = 1; i <= length; i++) {
			int seed = (int) Math.round(Math.random() * max);
			numbers[i-1] = seed;
			if(i>= 20 && i%20 == 0)
				System.out.println(numbers[i-1]);
			else
				System.out.print(numbers[i-1]);
			if (i < numbers.length) {
				System.out.print(",");
			}
		}
		System.out.println("]");
		return numbers;
	}

	static class LongestSerial {
		private int pos;
		private int len;

		LongestSerial(int pos, int len) {
			this.pos = pos;
			this.len = len;
		}
	}

	/**
	 * Divide and conquer the number array to find longest serial in this array,
	 * such as the array =[1,2,3,4,5,6,7,8,8,8,9,10]; so the longest serial is
	 * '8,8,8', the size is 3
	 * 
	 * @param args
	 * @throws InterruptedException
	 */
	public static void main(String[] args) throws InterruptedException {
		//default length of number array
		int arrayLen = 100;
		//default number scope 
		int maxUnit = 20;
		// parse the parameter, and assign them
		if (args != null & args.length > 0) {
			boolean correct = true;
			for (int i = 0; i < args.length; i++) {
				if ("-length".equals(args[i])) {
					if (args[i + 1] != null) {
						arrayLen = Integer.valueOf(args[i + 1]);
						i++;
						continue;
					} else {
						correct = false;
						break;
					}
				}

				if ("-unit".equals(args[i])) {
					if (args[i + 1] != null) {
						maxUnit = Integer.valueOf(args[i + 1]);
						i++;
						continue;
					} else {
						correct = false;
						break;
					}
				}
				correct = false;
				break;

			}

			if (!correct) {
				System.out.println("Usage: " + PrimeSearching.class.getName()
						+ " -length number -unit number ");
				return;
			}
		}
		
		int[] numbers = RandomCreateArray(arrayLen,maxUnit);

		ForkJoinPool fjPool = new ForkJoinPool();
		// import!
		// suppose the longest serial is first element
		int initSerialPos = 0;
		int initSerialLen = 1;
		LongestSerial result = new LongestSerial(initSerialPos, initSerialLen);
		LongestSerialSearch search = new LongestSerialSearch(numbers, 0,
				arrayLen - 1, result);
		fjPool.invoke(search);
//		fjPool.awaitTermination(2, TimeUnit.SECONDS);
		System.out.println("Search result as below...");
		System.out.println("---------------------------------------");
		System.out.println("The length of longest serial is "
				+ result.len);
		System.out.println("Its unit number is " + numbers[result.pos]);
		System.out.println("---------------------------------------");

	}
}
